package leetcode.day_2020_11_16_11_22;

public class L_5 {
    public static void main(String[] args) {
        String s = "abbd";
        System.out.println(longestPalindrome2(s));
    }

    /**
     * 暴力破解法
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        if(s.length() < 2)
            return s;
        int maxLen = 1;
        int beginIndex = 0;
        char[] sArr = s.toCharArray();
        for(int i=0; i<sArr.length-1; i++) {
            for(int j=i; j<sArr.length; j++) {
                if(j-i+1>maxLen && isPalindrome(sArr, i, j)) {
                    maxLen = j-i+1;
                    beginIndex = i;
                }
            }
        }
        return s.substring(beginIndex, beginIndex+maxLen);
    }

    public static boolean isPalindrome(char[] s, int begin, int end) {
        while (begin <= end) {
            if (s[begin] != s[end])
                return false;
            begin++;
            end--;
        }
        return true;
    }

    public static String longestPalindrome2(String s){
        if(s.length() < 2)
            return s;
        char[] sArr = s.toCharArray();
        boolean[][] dp = new boolean[sArr.length][sArr.length];
        int maxlen = 1;
        int begin = 0;
        for(int k=0; k<sArr.length; k++)
            dp[k][k] = true;
        for(int j=1; j<sArr.length; j++) {
            for(int i=0; i<sArr.length; i++) {
                if(sArr[i] != sArr[j]){
                    dp[i][j] = false;
                }else {
                    if(j-i <3){
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if(dp[i][j] && j-i+1>maxlen){
                    maxlen = j-i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin+maxlen);
    }
}
